{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.10-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "输入初始土地栽花情况flowerbed数组：\n",
      "Gen 0 :  [0 0 1 0 1 0 0 1 0 0 0] ---------- fitness: 3\n",
      "Gen 1 :  [1 0 1 0 1 0 0 1 0 1 0] ---------- fitness: 5\n",
      "Gen 2 :  [1 0 1 0 1 0 0 1 0 0 1] ---------- fitness: 5\n",
      "Gen 3 :  [1 0 1 0 1 0 0 1 0 1 0] ---------- fitness: 5\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "import re\n",
    "# import matplotlib.pyplot as plt\n",
    "flowerbed=[]\n",
    "# flowerbed = [1,0,0,0,1]\n",
    "print(\"输入初始土地栽花情况flowerbed数组：\")\n",
    "# flowerbed = [1,0,0,0,1]\n",
    "flowerbed = [0,0,1,0,1,0,0,1,0,0,0]\n",
    "# flowerbed = [0,0,0,1,0,0,1,0,0,0,1]\n",
    "n=int(input('输入栽入花的数量'))\n",
    "TARGET_PLAN = flowerbed      # target DNA\n",
    "\n",
    "POP_SIZE = 300                      # population size\n",
    "CROSS_RATE = 0.5                    # mating probability (DNA crossover)\n",
    "MUTATION_RATE = 0.1                # mutation probability\n",
    "N_GENERATIONS = 500\n",
    "\n",
    "DNA_SIZE = len(TARGET_PLAN)\n",
    "\n",
    "origin_pop=flowerbed*POP_SIZE\n",
    "origin_pop=np.array(origin_pop)\n",
    "origin_pop=origin_pop.reshape(POP_SIZE,-1)\n",
    "\n",
    "class GA(object):\n",
    "    def __init__(self, DNA_size,  mutation_rate, pop_size):\n",
    "        self.DNA_size = DNA_size\n",
    "        # self.cross_rate = cross_rate\n",
    "        self.mutate_rate = mutation_rate\n",
    "        self.pop_size = pop_size\n",
    "        self.pop = origin_pop\n",
    "\n",
    "    def get_fitness(self):                      # 最重点的计算适应度\n",
    "        ###首先是体现出相邻的1是不行的，即硬约束\n",
    "        ### 惩罚为   *-1000000\n",
    "        fitness_list=[]\n",
    "        ex='1 1'\n",
    "        for individual in self.pop:\n",
    "            # print(individual)    \n",
    "            error_result=re.findall(ex,str(individual),re.S)\n",
    "            loss_num=len(error_result)\n",
    "            # print(loss_num)\n",
    "            ###还是选择不对就适应度归0，比较好,便于概率处理\n",
    "            # loss_fit=-1000000*loss_num\n",
    "            ###接着是体现出种的越多越好，即硬约束\n",
    "            ### self.pop 为300个体\n",
    "            fit_count=sum(individual)\n",
    "            if loss_num>0:\n",
    "                fit_count=0\n",
    "            # fit_count=sum(individual)+loss_fit\n",
    "            fitness_list.append(fit_count)\n",
    "        return np.array(fitness_list)\n",
    "\n",
    "    def select(self):\n",
    "        # fitness = self.get_fitness() + 1e-4     # add a small amount to avoid all zero fitness\n",
    "        \n",
    "        ###如何挑选出得分前10%的个体，传到下一代\n",
    "        ##更新fitness,保证概率为正\n",
    "        # fitness=[i for i in fitness if i<0: i=0]\n",
    "        # print(fitness)\n",
    "        idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True, p=fitness/fitness.sum())###即从编号range(pop_size)的个体中有放回的抽样,抽出pop_size个\n",
    "        return self.pop[idx]\n",
    "\n",
    "    # def crossover(self, parent, pop):###求简单，不需要\n",
    "    #     if np.random.rand() < self.cross_rate:\n",
    "    #         i_ = np.random.randint(0, self.pop_size, size=1)                        # select another individual from pop\n",
    "    #         cross_points = np.random.randint(0, 2, self.DNA_size).astype(np.bool)   # choose crossover points\n",
    "    #         parent[cross_points] = pop[i_, cross_points]                            # mating and produce one child\n",
    "    #     return parent\n",
    "\n",
    "    def mutate(self, child):###要保证的是只能由0变1，也就是再种树，不能1变0。不改变原来结果\n",
    "        for point in range(self.DNA_size):##每一个点都可能变为1，即原来为1则没突变\n",
    "            if np.random.rand() < self.mutate_rate:\n",
    "                child[point] = 1  # 即此节点变为种树\n",
    "        return child\n",
    "\n",
    "    def evolve(self):\n",
    "        pop = self.select()\n",
    "        # pop_copy = pop.copy()###要保持原样本？？？\n",
    "        # print('前',pop)\n",
    "        for parent in pop:  # for every parent\n",
    "            # child = self.crossover(parent, pop_copy)\n",
    "            child = self.mutate(parent)\n",
    "            parent[:] = child\n",
    "        # print('后',pop)\n",
    "        self.pop = pop\n",
    "###实例化对象\n",
    "ga = GA(DNA_size=DNA_SIZE, mutation_rate=MUTATION_RATE, pop_size=POP_SIZE)  ###初始化\n",
    "best_fit=[]\n",
    "# best_fit=[0,1e-5]\n",
    "\n",
    "for generation in range(N_GENERATIONS):\n",
    "    fitness = ga.get_fitness()\n",
    "    # print(fitness)\n",
    "    # print(np.argmax(fitness))\n",
    "    best_index = np.argmax(fitness)\n",
    "    best_fit.append( fitness[best_index] )\n",
    "    best_result = ga.pop[np.argmax(fitness)]###返回本代适应度最高个体\n",
    "    print('Gen', generation, ': ', best_result ,'-'*10,'fitness:' , best_fit[generation])\n",
    "    # print('Gen', generation, ': ', best_result)\n",
    "        ###终止的指标，很重要很重要，三代没有变化则停止\n",
    "    if generation>=2:\n",
    "        if best_fit[generation] == best_fit[generation-1] and best_fit[generation-1] == best_fit[generation-2]:\n",
    "            break  \n",
    "    ga.evolve()\n",
    "# print(best_fit)\n",
    "# print(sum(flowerbed))\n",
    "# print(n)\n",
    "if best_fit[-1]-sum(flowerbed)<n:\n",
    "    print(\"False\")\n",
    "else:\n",
    "    print(\"True\")\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0]"
      ]
     },
     "metadata": {},
     "execution_count": 12
    }
   ],
   "source": [
    "flowerbed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}